import java.util.ArrayList;
import java.util.List;

/**
 * 971. 翻转二叉树以匹配先序遍历
 * https://leetcode-cn.com/problems/flip-binary-tree-to-match-preorder-traversal/
 */
public class Solutions_971 {
    public static void main(String[] args) {
//        String str = "[1 2 3]";
        String str = "[1 2]";
        TreeNode root = MyTreeNodeUtils.deserialize(str);
//        int[] voyage = {1, 2, 3};  // output: []  不需要翻转
//        int[] voyage = {1, 3, 2};  // output: [1]  需要翻转 1 的两个子节点

        int[] voyage = {1, 2};  // output: []
//        int[] voyage = {2, 1};  // output: [-1]

        List<Integer> result = flipMatchVoyage(root, voyage);
        System.out.println(result);
    }

    private static int idx = 0;
    private static List<Integer> res = null;
    private static int[] arr = null;
    public static List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        idx = 0;
        res = new ArrayList<>();
        arr = voyage;
        boolean flag = dfs(root);

        if (!flag) {
            // 无法完成匹配的情况
            res.clear();
            res.add(-1);
        }
        return res;
    }

    public static boolean dfs(TreeNode root) {
        if (root == null) {
            // 已经匹配到了叶子节点的子节点
            return true;
        }
        // 每匹配一次，idx 加 1
        if (root.val != arr[idx ++]) {
            // 根节点值不匹配
            return false;
        }
        if (root.left != null && root.left.val != arr[idx]) {
            // 需要交换左右子树
            res.add(root.val);
            return dfs(root.right) && dfs(root.left);
        } else {
            // 不需要交换
            return dfs(root.left) && dfs(root.right);
        }
    }
}
